﻿//力扣：814. 二叉树剪枝
//https://leetcode.cn/problems/binary-tree-pruning/description/


//方法：（dfs - 后序遍历）：
//后序遍历按照左⼦树、右⼦树、根节点的顺序遍历⼆叉树的所有节点，通常⽤于⽗节点的状态依赖于⼦节点状态的题⽬。

//算法原理：
//如果我们选择从上往下删除，我们需要收集左右⼦树的信息，这可能导致代码编写相对困难。然⽽，通过观察我们可以发现，
//如果我们先删除最底部的叶⼦节点，然后再处理删除后的节点，最终的结果并不会受到影响。

//因此，我们可以采⽤后序遍历的⽅式来解决这个问题。在后序遍历中，我们先处理左⼦树，然后处理右⼦树，最后再处理当前节点。
//在处理当前节点时，我们可以判断其是否为叶⼦节点且其值是否为 0，如果满⾜条件，我们可以删除当前节点。

//• 需要注意的是，在删除叶⼦节点时，其⽗节点很可能会成为新的叶⼦节点。因此，在处理完⼦节点后，我们仍然需要处理当前节点。
//    这也是为什么选择后序遍历的原因（后序遍历⾸先遍历到的⼀定是叶⼦节点）。
//• 通过使⽤后序遍历，我们可以逐步删除叶⼦节点，并且保证删除后的节点仍然满⾜删除操作的要求。
//    这样，我们可以较为⽅便地实现删除操作，⽽不会影响最终的结果。
//• 若在处理结束后所有叶⼦节点的值均为 1，则所有⼦树均包含 1，此时可以返回。

//算法流程：
//递归函数设计：void dfs(TreeNode * &root)
//1. 返回值：⽆；
//2. 参数 ：当前需要处理的节点；
//3. 函数作⽤：判断当前节点是否需要删除，若需要删除，则删除当前节点。

//后序遍历的主要流程：
//1. 递归出⼝：当传⼊节点为空时，不做任何处理；
//2. 递归处理左⼦树；
//3. 递归处理右⼦树；
//4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶⼦节点），并且节点的值为 0：
//    a.如果是，就删除掉；
//    b.如果不是，就不做任何处理。
class Solution 
{
public:
    TreeNode* pruneTree(TreeNode* root)
    {
        if (root == nullptr)
        {
            return nullptr;                         // 空节点直接返回 nullptr
        }

        // 递归剪枝左子树和右子树
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);

        // 如果当前节点是 0，且左右子树都为空，删除当前节点
        if (root->val == 0 && root->left == nullptr && root->right == nullptr)
        {
            root = nullptr;                         // 将当前节点置为 nullptr
        }

        return root;                                // 返回剪枝后的树
    }
};